群论笔记 06

keep in mind that,

1. many morphism in orginal map to one morphism in target category is OK. because Functor is mappings, also means that he is functions, functions may shrink things, may collapse things, many:1 is function, right! it's OK. And any other attricute we talked about functions, is also suited for Functors. Functors doesn't have to be surjective or injective. But you CAN NOT destroy the connection(arrow) of original category.
2. Functors can collapse the objects, like 30 objects in original but 3 objects in target category.
3. EndoFunctor : original Category and target category are same one(no reqiurement that they should be different categories)

#+BEGIN_QUOTE Faithfull Functor is injective on hom-set << Full Functor is surjective on hom-set << this two defnition ONLY related to home-set, not objects.

#+END_QUOTE

1. Picking Functors: A functor just "picking" object from target category:

arrows in this picture above, is two Functors, keep attention.

this is something like functions of singleton set

1. Constant Funtors(Δc): All collapse to black hole

arrows in this picture above, are Functors, keep attention.

1. EndoFunctor : original Category and target category are same one(no reqiurement that they should be different categories) In scala and Haskell, Functors are EndoFunctors, because they are all summed to ONLY have one category.

Mabe a

new cate:      Maybe a            Maybe b
                  ^                   ^ 
                  .                   . 
                  .Maybe              .Maybe
                  .                   . 
                  .                   . 
original cate:    a                   b

Functor is a mapping between whole types, yes, type constructor.

List[A]

List is a Functor, he is a type constructor, which mapping from category A to category List[A]

Option[A]

Option is a Functor, he is a type constructor, which mapping from category A to category Option[A]

This is only one use of functor, just mapping the objects(type). Functor can also mapping morphism

Indeed, functor can be a mapping between (mapping of type) and (mapping of type constructor)

fmap::(a->b) -> (Maybe a -> Maybe b)

new cate:       Maybe a ---------->Maybe b
                   ^        ^          ^ 
                   .        .          . 
                   .Maybe   .fmap      .Maybe
                   .        .          . 
                   .        .          . 
original cate:     a --------------->  b

in an abstract way of commutative graph:

when programming haskell ,we are straying from mathematics. Let's define a Functor: the definition below is an abstract Functor, or we define the template.

data Maybe a = Nothing | Just a
fmap :: (a->b) -> (Maybe a -> Maybe b)
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

This is a typical way of implementing functors, the functor usually has somthing of type a inside, then you can apply this function to the inside of of a functor, in a moment I'll talk about this next lecture.

Instresting, professor ask a question: fmap f Nothing = ? can be somthing else other than Nothing? then he says something about the polymorphism:

Can it be something "it's Nothing unless A is integer."

ad-hot polymorphism: for Integer do one thing, for non-Integer do other things.

because kinds of polymorphism supported by Haskell is limited, so there is more restriction here we can do.

notice that 1st id is the orignial 2nd is for target category, and symbol = means equal as it is in math, What is "function equal" means, yes it's means that they can replace with each other on two sids of "=", when you find somewhere one is called, you can replace directly by the other one, means they are actually the same thing.

• professor says that macro in C++ is an example of inline;
• replace equal method between each other refactory
• inline and refactory in imperative language is difficult; but in functional language is not so annoy

TARGET: identity [ ] 1. fmap id = id - [ ] 1. fmap id Nothing = Nothing - [ ] 2. fmap id (Just x) = Just x [-] 2. fmap (g/f) = fmap g / fmap f

PROVE TARGET

// fmap is the general name of Functor in Haskell
// f here is the function of original category
// we now need to justify the identity: fmap id = id
// if we want to do this, we need to ensure

data Maybe a = Nothing | Just a
fmap :: (a->b) -> (Maybe a -> Maybe b)
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

id x = x

// also x = id x
// id Nothing = Nothing
// fmap f Nothing = Nothing

fmap id Nothing = Nothing

// fmap id Nothing = Nothing = id Nothing
// fmap id (Just x) = Just(id x) = Just x

So you can see that from code block above

TARGET: identity [x] 1. fmap id = id - [x] 1.1 fmap id Nothing = Nothing - [x] 1.2 fmap id (Just x) = Just x [ ] 2. fmap (g/f) = fmap g / fmap f

tips: keep in mind that, "=" in quotion block above , is as it is in mathematic, means equal

same with above, skipped here. then professor refer to polymorphism again, that "you can get ensurement for free of the composition by polymorphism in hasekll"

here are some reference to blogs about profunctor: 1. contravariant Functors - An Intuition 2. profunctor and polymorphism

when you define a Functor in Haskell, you think you truely get a functor, but you will find not that. Because in the next lecture you will most of the stuff you come up with is automatically a functor, like algebraic datatypes, it's automatically a functor.

Functor have his laws(preserve structure:mapping objects/functions, keep the composition and identity). While monad also has its own laws.

In this sense, many collection with map function build in as API is a Functor:

val c = List(1,2,3,4)
c.Map(a => a + 10) // List(11,12,13,14)

let's go back to the code about a list, of previous lecture:

data List a = Nil | cons a (List a) It is so self-explanatory , and give a recursive definition of List > - "what is a List" > - "it's empty or concate a value with a List"

class Functor f where // abstract class
  fmap :: (a->b) -> (fa->fb) // here f is a type constructor

data List a = Nil | cons a (List a) // List is a type constructor

instance Functor List where
  fmap g Nil = Nil
  fmap g (cons head tail) = cons (g head) (fmap g tail) // funny

last 3 line of code is just the pattern match function, something like scala case match clause. So, you can see somthing like cons head tail. And, head and tail are two variables used in pattern match clause, will be directly assign proper value when matched.

def fn(lst: List[Int]) = lst match{
  case Nil => println("empty")
  case head :: tail => println("head: " + head + ", tail: " + tail)
}

Note that , fmap g tail is a recursive funtion using again fmap g

this code above is the map API of List, and map of List is just one implementation of fmap.

type Reader r a = r->a

type construnctor can be an "Symbol" itself: > 1. List[Int]: List construct List[Int] from Int > 2. Option[Int]: Option construct Option[Int] from Int > 3. Seq[Int]: Seq construct Seq[Int] from Int

List,=Option=,=Seq=, are all Characters; but type constructor also can be "Symbol", like ->,==>=,=::=,=+:=, and even more we use char-type-constructor as prefix, here we can use symbol-type-constructor as infix:

1. =>[Int,Int]: => constuct Function[Int,Int] from Int,Int
2. ::[Int,List[Int]]: :: construct List[Int] from Int,List[Int]
3. +:[Int,Seq[Int]]: +: construct Seq[Int] from Int,Seq[Int]

another problem, we never talk about two parameter type constuctor, yes,but we can just fix one type and say we only care about the second, like we can do that in partial applied function.

1. Int => : is a type constructor on Int
2. Int :: : is a type constructor on List[Int]
3. Int +: : is a type constructor on Seq[Int]

(a->b) -> (Fa->Fb)
is same with
((a->b) -> Fa) -> Fb
F <=> r->
(a->b) -> (r->a) -> (r->b)

In scala, Function1[+A,-B] is just a two parameter type constructor, it will reduce to one type constructor when fix first parameter:

then Reader r is our Functor.

This is like curry or partial applied function, you have 2 arguments(must be 2 parameter list in scala),you fix one argument and it becomes a function of one argument here.

class Functor f where // abstract class
  fmap :: (a->b) -> (fa->fb) // here f is a type constructor

type Reader r a = r -> a // 'r ->' is a type constructor

fmap :: (a -> b) -> (r-> a) -> (r-> b)
// h is (a->b); g is (r->a)
fmap h g = h * g = (*) h g // this you get a function: r -> b
// fmap = * 

fmap h g = h * g = (/) h g then fmap = /

this is function, you only have parameter h and g, so in your function body(all things after '=') should use and ONLY use this two parameters.

you can compare these two Functor

class Functor f where // abstract class
  fmap :: (a->b) -> (fa->fb) // here f is a type constructor

data List a = Nil | cons a (List a) // List is a type constructor

instance Functor List where
  fmap h Nil = Nil
  fmap h (cons head tail) = cons (h head) (fmap h tail) // funny

serious :| , you must keep in mind that when you are ambiguous with code above, that is all the chars occur in the codes are type variable, don't think them as value, then you can understantd: 1. why r->b = h * g 2. why h (cons head tail) is pattern match.

fmap h Nil = Nil
fmap h (cons head tail) = cons (h head) (fmap h tail) // funny

pattern match in Haskell is something like code above, which in scala we must use case match clause, so you know that why in scala case clause is also a function in scala, it's truly imitate the stype and principle of the Haskell.

pattern match in haskell used like function pattern match in scala — case clause also can be used like function

What is actually a List, What List is on the ground? you know that, * Boolean can be memoized. * List/String can not be memoized.

List can have inifinite elements, we may ask how was List represeted inside the computer? OK, it is represented by function. It just produce elements, but function can also produce element. Refer to List, what you know is just a symbol "List", and you give some values as initialization, like List(1,2,3), then you ask value by given loacation like l(2), so: * List(1,2,3) is just giving the domain of function * l(2) is just calling function by giving an input

so, List is Function,and Function is a general List

good reference:

type constructor using in function

From the link to graphic, we can see that: > * List[\_] is (->) > * Map[/,/] or Function1[/,/] is (->->/) > / Map[Int,\_] or Function1[Int,\_] is (->) > * Functor[F[\_]] is ((->)->*)

*->* This says: given one type, produce another. For instance, given String produce the type List[String]. All the type constructor list above, can apply partially: Map[Int,\_] or Function1[Int,\_] is (->)

Everything in haskell, is just thunk, there is no hard core distinction, then what function type is in category theory actually, you'll see that function type is just an exponential data type.

so, Functin is just a exponential data type

Many data: "may or" is sum type; collection is product type; function is exponential type;

(a->b) -> (Fa->Fb)

1. F = List : is a container(functor) implemented by product-datatype
2. F = r -> : is a container(functor) implemented by exponential-datetype